class Instruction(str):
	pass

class Tape:
	"""A unidimensional infinite tape of characters with a head"""
	RIGHT = +1
	LEFT = -1
	NO_MOVE = 0
	def __str__(self):
		"""The content of the tape, with the current position indicated by vertical bars"""
		return ''.join(self.leftList + ['|', self.currentValue, '|'] + self.rightList[::-1])
	def __init__(self,  defaultValue=None, content=None):
		"""Construct a new tape with the specified content and the default value elsewhere"""
		self.defaultValue = defaultValue if defaultValue else None
		if content:
			self.leftList, self.currentValue, self.rightList = content.split('|')
			self.leftList, self.rightList = [Instruction(i) for i in self.leftList], [Instruction(i) for i in self.rightList]
	def tapeCopy(self):
		t = Tape()
		t.leftList, t.currentValue, t.rightList = self.leftList, self.currentValue, self.rightList
		return t
	def __iter__(self):
		for i in self.leftList:
				yield i, False
		yield self.currentValue, True
		for i in self.rightList[::-1]:
				yield i, False
	def move(self, step):
		"""Move the tape"""
		if step == Tape.NO_MOVE: # do not move
			pass
		elif step in [Tape.LEFT, Tape.RIGHT]: # move left or right
			toAppend, toPop = (self.leftList, self.rightList) if step==Tape.RIGHT else (self.rightList, self.leftList)
			toAppend.append(self.currentValue) # append the current state to a lateral list
			try:
				self.currentValue = toPop.pop() # update the current position
			except IndexError:
				self.currentValue = self.defaultValue # if the list is empty, use the default value
		else: # invalid move
			raise ValueError('the step {} is not a valid value'.format(step))

class Table(dict):
	def __bool__(self):
		instructions = None
		for state in self:
			if self[state]:
				if instructions:
					if set(self[state].keys()) != instructions:
						return False
				else:
					instructions = set(self[state].keys())
		for state in self:
			if self[state]:
				for instruction in self[state]:
					s, v, m = self[state][instruction]
					if s not in self.keys():
						return False
					if v not in instructions:
						return False
					if m not in (Tape.LEFT, Tape.RIGHT, Tape.NO_MOVE):
						return False
		return True

class Machine:
	"""A turing machine with the specified transition table, list of final states, tape and initial state"""
	def __init__(self, transition, initialState, tape):
		self.transition = transition
		self.currentState = initialState
		self.tape = tape
	def isRunning(self):
		return self.transition[self.currentState]
	def __next__(self):
		if self.isRunning():
			self.currentState, self.tape.currentValue, step = self.transition[self.currentState][self.tape.currentValue]
			self.tape.move(step)
		else:
			raise StopIteration
